In this study, we address the problem of answering queries over apeer-to-peer system of taxonomy-based sources. A taxonomy states subsumptionrelationships between negation-free DNF formulas on terms and negation-freeconjunctions of terms. To the end of laying the foundations of our study, wefirst consider the centralized case, deriving the complexity of the decisionproblem and of query evaluation. We conclude by presenting an algorithm that isefficient in data complexity and is based on hypergraphs. More expressive formsof taxonomies are also investigated, which however lead to intractability. Wethen move to the distributed case, and introduce a logical model of a networkof taxonomy-based sources. On such network, a distributed version of thecentralized algorithm is then presented, based on a message passing paradigm,and its correctness is proved. We finally discuss optimization issues, andrelate our work to the literature.
展开▼
